package homework;

import java.util.*;

class Node{
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        Node node1 = new Node(7);
        Node node2 = new Node(13);
        Node node3 = new Node(11);
        Node node4 = new Node(10);
        Node node5 = new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node1.random = null;
        node2.random = node1;
        node3.random = node5;
        node4.random = node3;
        node5.random = node1;

        Node newLinkedList = s.copyRandomList(node1);
        System.out.println();
    }
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        //先把新链表节点交替插入到旧链表的后面
        while (cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        //再写新节点的random的区域
        cur = head;
        while (cur != null) {
            Node newCur = cur.next;
            if (cur.random != null) {
                newCur.random = cur.random.next;
            }
            cur = newCur.next;
        }
        //再把新链表拆出来
        cur = head;
        Node newHead = cur.next;
        Node newCur = cur.next;
        while (cur != null) {
            cur.next = newCur.next;
            cur = cur.next;
            if (cur == null) {
                break;
            }
            newCur.next = cur.next;
            newCur = newCur.next;
        }
        return newHead;
    }
    public static void main1(String[] args) {
        Solution s = new Solution();
        String[] words = {"i","love","leetcode","i","love","coding"};
        s.topKFrequent(words, 2);
        System.out.println();
    }
    public List<String> topKFrequent(String[] words, int k) {
        //先建立键值对，把键值对的关系梳理好
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            if(!map.containsKey(words[i])){
                map.put(words[i], 1);
            }else{
                int count = map.get(words[i]);
                map.put(words[i], count + 1);
            }
        }
        ValueComparator comparator = new ValueComparator();
        PriorityQueue<Map.Entry<String, Integer>> topKWords = new PriorityQueue<>(comparator);
        //再建立小根堆，指定比较方式，把前K个单词放进去
        for(Map.Entry<String, Integer> entry : map.entrySet()){
            if(topKWords.size() < k){
                topKWords.offer(entry);
            }else{
                Map.Entry<String, Integer> keyValue = topKWords.peek();
                if(entry.getValue() > keyValue.getValue()){
                    topKWords.poll();
                    topKWords.offer(entry);
                }else{
                    if(entry.getValue() == keyValue.getValue()){
                        if(entry.getKey().compareTo(keyValue.getKey()) < 0){
                            topKWords.poll();
                            topKWords.offer(entry);
                        }
                    }
                }
            }
        }
        //再取出单词
        List<String> list = new ArrayList<>();
        for(int j = 0; j < k; j++){
            list.add(topKWords.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
    static class ValueComparator implements Comparator {
        public int compare(Object o1, Object o2){
            return ((Map.Entry<String, Integer>)o1).getValue() - ((Map.Entry<String, Integer>)o2).getValue();
        }
    }
}